{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Parallel Courses III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #并行课程 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;，表示有&nbsp;<code>n</code>&nbsp;节课，课程编号从&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;。同时给你一个二维整数数组&nbsp;<code>relations</code>&nbsp;，其中&nbsp;<code>relations[j] = [prevCourse<sub>j</sub>, nextCourse<sub>j</sub>]</code>&nbsp;，表示课程&nbsp;<code>prevCourse<sub>j</sub></code>&nbsp;必须在课程&nbsp;<code>nextCourse<sub>j</sub></code>&nbsp;<strong>之前</strong>&nbsp;完成（先修课的关系）。同时给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>time</code>&nbsp;，其中&nbsp;<code>time[i]</code>&nbsp;表示完成第&nbsp;<code>(i+1)</code>&nbsp;门课程需要花费的 <strong>月份</strong>&nbsp;数。</p>\n",
    "\n",
    "<p>请你根据以下规则算出完成所有课程所需要的 <strong>最少</strong>&nbsp;月份数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果一门课的所有先修课都已经完成，你可以在 <strong>任意</strong>&nbsp;时间开始这门课程。</li>\n",
    "\t<li>你可以&nbsp;<strong>同时</strong>&nbsp;上&nbsp;<strong>任意门课程</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回完成所有课程所需要的 <strong>最少</strong>&nbsp;月份数。</p>\n",
    "\n",
    "<p><strong>注意：</strong>测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/07/ex1.png\" style=\"width: 392px; height: 232px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, relations = [[1,3],[2,3]], time = [3,2,5]\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。\n",
    "你可以在月份 0 同时开始课程 1 和 2 。\n",
    "课程 1 花费 3 个月，课程 2 花费 2 个月。\n",
    "所以，最早开始课程 3 的时间是月份 3 ，完成所有课程所需时间为 3 + 5 = 8 个月。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/07/ex2.png\" style=\"width: 500px; height: 365px;\"></strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]\n",
    "<b>输出：</b>12\n",
    "<b>解释：</b>上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。\n",
    "你可以在月份 0 同时开始课程 1 ，2 和 3 。\n",
    "在月份 1，2 和 3 分别完成这三门课程。\n",
    "课程 4 需在课程 3 之后开始，也就是 3 个月后。课程 4 在 3 + 4 = 7 月完成。\n",
    "课程 5 需在课程 1，2，3 和 4 之后开始，也就是在 max(1,2,3,7) = 7 月开始。\n",
    "所以完成所有课程所需的最少时间为 7 + 5 = 12 个月。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= relations.length &lt;= min(n * (n - 1) / 2, 5 * 10<sup>4</sup>)</code></li>\n",
    "\t<li><code>relations[j].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= prevCourse<sub>j</sub>, nextCourse<sub>j</sub> &lt;= n</code></li>\n",
    "\t<li><code>prevCourse<sub>j</sub> != nextCourse<sub>j</sub></code></li>\n",
    "\t<li>所有的先修课程对&nbsp;<code>[prevCourse<sub>j</sub>, nextCourse<sub>j</sub>]</code>&nbsp;都是 <strong>互不相同</strong>&nbsp;的。</li>\n",
    "\t<li><code>time.length == n</code></li>\n",
    "\t<li><code>1 &lt;= time[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>先修课程图是一个有向无环图。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [parallel-courses-iii](https://leetcode.cn/problems/parallel-courses-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [parallel-courses-iii](https://leetcode.cn/problems/parallel-courses-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[1,3],[2,3]]\\n[3,2,5]', '5\\n[[1,5],[2,5],[3,5],[3,4],[4,5]]\\n[1,2,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import DefaultDict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topologicalSort(\n",
    "        self, n: int, in_degree: DefaultDict[int, int], next: DefaultDict[int, List[int]], time: List[int]\n",
    "    ) -> int:\n",
    "        total_time: int = 0\n",
    "        start_time: List[int] = [0] * n\n",
    "        end_time: List[int] = [0] * n\n",
    "        cur_level: List[int] = []\n",
    "        next_level: List[int] = [i for i, n in enumerate(in_degree) if n == 0]\n",
    "\n",
    "        while len(next_level) > 0:\n",
    "            cur_level, next_level = next_level, cur_level\n",
    "\n",
    "            for u in cur_level:\n",
    "                end_time[u] = start_time[u] + time[u]\n",
    "                total_time = max(total_time, end_time[u])\n",
    "                for v in next[u]:\n",
    "                    start_time[v] = max(start_time[v], end_time[u])\n",
    "                    in_degree[v] -= 1\n",
    "                    if in_degree[v] == 0:\n",
    "                        next_level.append(v)\n",
    "\n",
    "            cur_level.clear()\n",
    "\n",
    "        return total_time\n",
    "\n",
    "\n",
    "    def buildGraph(\n",
    "        self, edges: List[List[int]], in_degree: DefaultDict[int, int], next: DefaultDict[int, List[int]]\n",
    "    ) -> None:\n",
    "        for u, v in edges:\n",
    "            in_degree[v - 1] += 1\n",
    "            next[u - 1].append(v - 1)\n",
    "\n",
    "\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        in_degree: List[int] = [0] * n\n",
    "        next: DefaultDict[int, List[int]] = defaultdict(list)\n",
    "        self.buildGraph(relations, in_degree, next)\n",
    "        return self.topologicalSort(n, in_degree, next, time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        graph = [ [] for _ in range(n)]\n",
    "        degree = [ 0 ]*n\n",
    "        for i,j in relations:\n",
    "            graph[i-1].append(j-1)\n",
    "            degree[j-1]+=1\n",
    "        \n",
    "        h = []\n",
    "\n",
    "        zeros = [  i for i in range(n) if degree[i] == 0 ]\n",
    "        for z in zeros:\n",
    "            heappush(h, (time[z],z) )\n",
    "        \n",
    "        while h:\n",
    "            t,z = heappop(h)\n",
    "            \n",
    "            for j in graph[z]:\n",
    "                degree[j] -= 1\n",
    "                if degree[j]==0:\n",
    "                    heappush(h,(time[j]+t,j))\n",
    "        \n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "每个课程的完成时间，与其前置课程的完成时间，存在递推关系。\n",
    "动态规划，\n",
    "f[u]=max(f[pre])+time[u-1]\n",
    "拓扑排序完成递推迭代过程，答案为max(f)\n",
    "\n",
    "错误的贪心思路：按照拓扑排序，每次修全部的入度为0的课程，每次花费时间是这些值的最大值。\n",
    "因为当前选择的课程，放在下次花费比它多的一些课程中完成，等于时间被“淹没”，整体能得到更小值，\n",
    "而入度为0的课程是动态规划的边界状态，递推下去不会错。\n",
    "'''\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, R: List[List[int]], time: List[int]) -> int:\n",
    "        g=[[]for _ in range(n)];ind=[0]*n;f=[0]*n;z=0\n",
    "        for u,v in R:u-=1;v-=1;g[u]+=[v];ind[v]+=1\n",
    "        q=deque([i for i in range(n)if ind[i]==0])\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            f[u]+=time[u];z=max(z,f[u])\n",
    "            for v in g[u]:\n",
    "                f[v]=max(f[v],f[u])\n",
    "                ind[v]-=1\n",
    "                if ind[v]==0:q.append(v)\n",
    "        return z\n",
    "\n",
    "        pres=[[]for _ in range(n)];ind=[0]*n\n",
    "        for u,v in R:u-=1;v-=1;pres[v]+=[u];ind[v]+=1\n",
    "        @cache\n",
    "        def f(u):\n",
    "            z=0\n",
    "            if ind[u]:\n",
    "                z=max(f(pre)for pre in pres[u])\n",
    "            return z+time[u]\n",
    "        return max(f(u)for u in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def minimumTime(n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        # 构建有向图\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "\n",
    "        # 记录每个节点的入度\n",
    "        indegree = [0] * (n + 1)\n",
    "\n",
    "        # 构建有向图和计算入度\n",
    "        for edge in relations:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            indegree[edge[1]] += 1\n",
    "\n",
    "        # 拓扑排序需要的队列\n",
    "        queue = deque()\n",
    "        ans = 0\n",
    "\n",
    "        # 找到入度为0的节点，加入队列\n",
    "        for i in range(1, n + 1):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "\n",
    "        # 记录每个节点的最小花费\n",
    "        cost = [0] * (n + 1)\n",
    "\n",
    "        # 拓扑排序\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            # 1 : time[0]\n",
    "            # x : time[x-1]\n",
    "            cost[cur] += time[cur - 1]\n",
    "            ans = max(ans, cost[cur])\n",
    "\n",
    "            # 遍历当前节点的邻居\n",
    "            for nxt in graph[cur]:\n",
    "                cost[nxt] = max(cost[nxt], cost[cur])\n",
    "\n",
    "                # 将邻居的入度减一\n",
    "                indegree[nxt] -= 1\n",
    "\n",
    "                # 如果邻居的入度变为0，则加入队列\n",
    "                if indegree[nxt] == 0:\n",
    "                    queue.append(nxt)\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 示例用法\n",
    "sol = Solution()\n",
    "n = 3\n",
    "relations = [[1, 3], [3, 2], [2, 1]]\n",
    "time = [3, 2, 5]\n",
    "result = sol.minimumTime(n, relations, time)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        time.insert(0,0)\n",
    "        ch=[[] for _ in range(n+1)]\n",
    "        ind=[0]*(n+1);dis=[0]*(n+1)\n",
    "        for u,v in relations:\n",
    "            ch[u].append(v)\n",
    "            ind[v]+=1\n",
    "        dq=deque()\n",
    "        res=0\n",
    "        for i in range(1,n+1):\n",
    "            if not ind[i]:\n",
    "                dq.append(i)\n",
    "                res=max(res,time[i])\n",
    "        while dq:\n",
    "            u=dq.popleft()\n",
    "            for v in ch[u]:\n",
    "                ind[v]-=1\n",
    "                dis[v]=max(dis[v],dis[u]+time[u])\n",
    "                if not ind[v]:\n",
    "                    dq.append(v)\n",
    "                    print(v)\n",
    "                    res=max(res,dis[v]+time[v])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        DUMMY = n\n",
    "        adjList = [[] for _ in range(n + 1)]\n",
    "        for a, b in relations:\n",
    "            adjList[a - 1].append(b - 1)\n",
    "        for i in range(n):\n",
    "            adjList[DUMMY].append(i)  # 虚拟源点指向所有点\n",
    "\n",
    "        dp = longestPathInDag(n + 1, adjList, lambda from_, to: time[to])\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "def longestPathInDag(\n",
    "    n: int, adjList: Sequence[Sequence[int]], getWeight: Optional[Callable[[int, int], int]] = None\n",
    ") -> List[int]:\n",
    "    \"\"\"返回DAG中每个点的最长路径长度.\"\"\"\n",
    "\n",
    "    def max(a: int, b: int) -> int:\n",
    "        return a if a > b else b\n",
    "\n",
    "    if getWeight is None:\n",
    "        getWeight = lambda x, y: 1  # noqa\n",
    "\n",
    "    indeg = [0] * n\n",
    "    for i in range(n):\n",
    "        for j in adjList[i]:\n",
    "            indeg[j] += 1\n",
    "\n",
    "    queue = deque(i for i in range(n) if indeg[i] == 0)\n",
    "    dp = [0] * n\n",
    "\n",
    "    while queue:\n",
    "        cur = queue.popleft()\n",
    "        for next_ in adjList[cur]:\n",
    "            dp[next_] = max(dp[next_], dp[cur] + getWeight(cur, next_))\n",
    "            indeg[next_] -= 1\n",
    "            if indeg[next_] == 0:\n",
    "                queue.append(next_)\n",
    "\n",
    "    return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        indegree = [0 for _ in range(n+1)]\n",
    "        for edge in relations:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            indegree[edge[1]] += 1\n",
    "        cost = [0 for _ in range(n+1)]\n",
    "        quene = [0 for _ in range(n)]\n",
    "        l = 0\n",
    "        r = 0\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            if indegree[i] == 0:\n",
    "                quene[r] = i\n",
    "                r += 1\n",
    "        while l < r:\n",
    "            cur = quene[l]\n",
    "            l += 1\n",
    "            cost[cur] += time[cur-1]\n",
    "            ans = max(ans, cost[cur])\n",
    "            for next in graph[cur]:\n",
    "                cost[next] = max(cost[next], cost[cur])\n",
    "                indegree[next] -= 1\n",
    "                if indegree[next] == 0:\n",
    "                    quene[r] = next\n",
    "                    r += 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        out=defaultdict(int)\n",
    "        edges=defaultdict(list)\n",
    "        for left,right in relations:\n",
    "            edges[left].append(right)\n",
    "            out[right]+=1\n",
    "        query,ans=[],0\n",
    "        for i in range(1,n+1):\n",
    "            if out[i]==0:\n",
    "                heappush(query,(time[i-1],i))\n",
    "                ans=max(time[i-1],ans)\n",
    "        \n",
    "        while query:\n",
    "            t,q=heappop(query)\n",
    "            for edge in edges[q]:\n",
    "                out[edge]-=1\n",
    "                if out[edge]==0:\n",
    "                    heappush(query,(time[edge-1]+t,edge))\n",
    "                    ans=max(ans,t+time[edge-1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        indeg = [0] * n \n",
    "        for a , b in relations:\n",
    "            g[a-1].append(b-1)\n",
    "            indeg[b-1] += 1\n",
    "        \n",
    "        q = deque()\n",
    "        f = [0] * n\n",
    "        ans = 0\n",
    "        for i ,(v,t) in enumerate(zip(indeg,time)):\n",
    "            if v == 0:\n",
    "                q.append(i)\n",
    "                f[i] = t\n",
    "                ans = max(ans,t)\n",
    "        \n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            for j in g[i]:\n",
    "                f[j] = max(f[j], f[i] + time[j])\n",
    "                ans = max(ans, f[j])\n",
    "                indeg[j] -=1\n",
    "                if indeg[j] == 0:\n",
    "                    q.append(j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        aft = [set() for i in range(n)]\n",
    "        pre = [0] * (n)\n",
    "        for a,b in relations:\n",
    "            aft[a-1].add(b-1)\n",
    "            pre[b-1] += 1\n",
    "        \n",
    "        cost = [0] * (n)\n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            if pre[i] == 0:\n",
    "                cost[i] = time[i]\n",
    "                queue.append(i)\n",
    "        \n",
    "        mmax = 0\n",
    "        while len(queue) > 0:\n",
    "            cur = queue[0]\n",
    "            queue = queue[1:]\n",
    "            mmax = max(mmax, cost[cur])\n",
    "            for b in aft[cur]:\n",
    "                pre[b] -= 1\n",
    "                costb = time[b] + cost[cur]\n",
    "                if cost[b] == 0 or cost[b] < costb:\n",
    "                    cost[b] = costb\n",
    "                if pre[b] == 0:\n",
    "                    queue.append(b)\n",
    "        return mmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        indegree = defaultdict(int)\n",
    "        parent = defaultdict(list)\n",
    "        for x, y in relations:\n",
    "            indegree[x - 1] += 1\n",
    "            parent[y - 1].append(x - 1)\n",
    "        q = [x for x in range(n) if x not in indegree]\n",
    "        fin = [0] * n\n",
    "        res = 0\n",
    "        for i in q:\n",
    "            fin[i] = time[i]\n",
    "            res = max(res, fin[i])\n",
    "        while q:\n",
    "            v = q.pop(0)\n",
    "            for i in parent.get(v, []):\n",
    "                fin[i] = max(fin[i], fin[v] + time[i])\n",
    "                res = max(res, fin[i])\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        time2=[]\n",
    "        for e in time:\n",
    "            time2.append([e,0])\n",
    "        d=defaultdict(int)\n",
    "        d2=defaultdict(list)\n",
    "        for i in range(1,n+1):\n",
    "            d[i]=0\n",
    "        for r in relations:\n",
    "            pc,nc=r\n",
    "            d[nc]+=1\n",
    "            d2[pc].append(nc)\n",
    "        l=[]\n",
    "        for k in d:\n",
    "            if d[k]==0:\n",
    "                l.append([k,0])\n",
    "        maxt=0\n",
    "        while(True):\n",
    "            l2=[]\n",
    "            for e in l:\n",
    "                c,pt=e\n",
    "                if pt+time2[c-1][0]>maxt:\n",
    "                    maxt=pt+time2[c-1][0]\n",
    "                for k in d2[c]:\n",
    "                    d[k]-=1\n",
    "                    if d[k]==0:\n",
    "                        if pt+time2[c-1][0]>time2[k-1][1]:\n",
    "                            time2[k-1][1]=pt+time2[c-1][0]\n",
    "                        l2.append([k,time2[k-1][1]])\n",
    "                    else:\n",
    "                        time2[k-1][1]=max(time2[k-1][1],pt+time2[c-1][0])\n",
    "            l=l2.copy()\n",
    "            if len(l)==0:return maxt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        adj = defaultdict(list)\n",
    "        degree = defaultdict(int)\n",
    "        for prevCourse, nextCourse in relations :\n",
    "            adj[prevCourse - 1].append(nextCourse - 1)\n",
    "            degree[nextCourse - 1] += 1\n",
    "        \n",
    "        spend = [0 for _ in range(n)]\n",
    "        dq = deque(i for i in range(n) if degree[i] == 0)\n",
    "        while dq :\n",
    "           course = dq.popleft()\n",
    "           spend[course] += time[course]\n",
    "           for nxt in adj[course] :\n",
    "                if spend[course] > spend[nxt] :\n",
    "                   spend[nxt] = spend[course]\n",
    "                degree[nxt] -= 1\n",
    "                if not degree[nxt] :\n",
    "                    dq.append(nxt)\n",
    "        \n",
    "        return max(spend)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        \n",
    "\n",
    "        ad={i:[] for i in range(1,n+1)}\n",
    "        completetime={i:0 for i in range(1,n+1)}\n",
    "        ind={i:0 for i in range(1,n+1)}\n",
    "\n",
    "        for s,e in relations:\n",
    "            ad[s].append(e)\n",
    "            ind[e]+=1\n",
    "        stack=[]\n",
    "        for i in range(1,n+1):\n",
    "            \n",
    "            if ind[i]==0:\n",
    "                stack.append(i)\n",
    "                completetime[i]=time[i-1]\n",
    "  \n",
    "   \n",
    "\n",
    "        while stack:\n",
    "            cur=stack.pop(0)\n",
    "            for nex in ad[cur]:\n",
    "                ind[nex]-=1\n",
    "                completetime[nex]=max(completetime[nex], completetime[cur] + time[nex - 1])\n",
    "                if ind[nex]==0:\n",
    "                    stack.append(nex)\n",
    "\n",
    "        return max(completetime.values())\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, idx):\n",
    "        self.idx = idx\n",
    "        self.neighbors = []\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int: \n",
    "        g = {}\n",
    "        ins = {}\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            g[i] = Node(i)\n",
    "            ins[i] = 0\n",
    "\n",
    "        for rel in relations:\n",
    "            A = rel[0]\n",
    "            B = rel[1]\n",
    "\n",
    "            node_A = g[A]\n",
    "            node_A.neighbors.append(B)\n",
    "\n",
    "            ins[B] += 1\n",
    "        \n",
    "        next_courses = []\n",
    "        current_month = 0\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            if ins[i] == 0:\n",
    "                time_needed = time[i - 1]\n",
    "                heapq.heappush(next_courses, [time_needed, i])\n",
    "        \n",
    "        while next_courses:\n",
    "            t, c = heapq.heappop(next_courses)\n",
    "            current_month = t\n",
    "\n",
    "            node_c = g[c]\n",
    "            c_neighbors = node_c.neighbors\n",
    "            for neighbor in c_neighbors:\n",
    "                ins[neighbor] -= 1\n",
    "                if ins[neighbor] == 0:\n",
    "                    time_needed = time[neighbor - 1]\n",
    "                    heapq.heappush(next_courses, [ current_month + time_needed, neighbor ])\n",
    "        \n",
    "        return current_month\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        if not relations:\n",
    "            return max(time)\n",
    "        mydic = {}\n",
    "        for i in range(1,n+1):\n",
    "            mydic[i] ={}\n",
    "            mydic[i]['in'] = 0\n",
    "            mydic[i]['out'] = []\n",
    "        for i in relations:\n",
    "            mydic[i[0]]['out'].append(i[1])\n",
    "            mydic[i[1]]['in'] += 1\n",
    "        on_study = []\n",
    "        times = 0\n",
    "        on_study_dic = {}                     \n",
    "        for i in mydic.keys():\n",
    "            if mydic[i]['in'] == 0:\n",
    "                heapq.heappush(on_study, [time[i-1]+times,i])\n",
    "\n",
    "\n",
    "\n",
    "        while on_study:\n",
    "            times,i= heapq.heappop(on_study)\n",
    "            for j in mydic[i]['out']:\n",
    "                mydic[j]['in'] -= 1\n",
    "                if mydic[j]['in'] == 0:\n",
    "                    heapq.heappush(on_study, [time[j-1]+times,j])\n",
    "            while on_study and on_study[0][0] == times:\n",
    "                times,i = heapq.heappop(on_study)\n",
    "                for j in mydic[i]['out']:\n",
    "                    mydic[j]['in'] -= 1\n",
    "                    if mydic[j]['in'] == 0:\n",
    "                        heapq.heappush(on_study, [time[j-1]+times,j])                                        \n",
    "        return times\n",
    "            \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "global time_all\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        \n",
    "        relist=list(range(1,n+1))\n",
    "        pre=dict(zip(range(1,n+1),[[] for i in range(n)]))\n",
    "        nextl=dict(zip(range(1,n+1),[[] for i in range(n)]))\n",
    "        pre_num=[0 for i in range(n)]\n",
    "        time_all=[0 for i in range(n)]\n",
    "        for i in relations:\n",
    "            # print(i)\n",
    "            pre[i[1]].append(i[0])\n",
    "            nextl[i[0]].append(i[1])\n",
    "            pre_num[i[1]-1]+=1\n",
    "\n",
    "        \n",
    "        pre0list=[i+1 for i in range(n) if pre_num[i]==0]\n",
    "        \n",
    "        while(len(pre0list)!=0):\n",
    "            pre0list1=pre0list\n",
    "            pre0list=[]\n",
    "            td={}\n",
    "            for i in pre0list1:\n",
    "                time_all[i-1]=time_all[i-1]+time[i-1]\n",
    "                for j in nextl[i]:\n",
    "                    if j not in td:\n",
    "                        td[j]=[]\n",
    "                    td[j].append(time_all[i-1])\n",
    "                    pre_num[j-1]=pre_num[j-1]-1\n",
    "                    if pre_num[j-1]==0:\n",
    "                        pre0list.append(j)\n",
    "            for i in td:\n",
    "                time_all[i-1]=max([time_all[i-1]]+td[i])\n",
    "            # print(time_all)\n",
    "        return max(time_all)\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        # for i in range(1,n+1):\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        next_list = [set() for _ in range(n + 1)]\n",
    "        pre_list = [set() for _ in range(n + 1)]\n",
    "\n",
    "        for relation in relations:\n",
    "            next_list[relation[0]].add(relation[1])\n",
    "            pre_list[relation[1]].add(relation[0])\n",
    "        begin_queue = Queue()\n",
    "        res = 0\n",
    "        real_time = [0] * (n + 1)\n",
    "        for index in range(1, n + 1):\n",
    "            if not pre_list[index]:\n",
    "                begin_queue.put(index)\n",
    "                real_time[index] = time[index - 1]\n",
    "                res = max(res, real_time[index])\n",
    "\n",
    "        while not begin_queue.empty():\n",
    "            header = begin_queue.get()\n",
    "            next_course_set = next_list[header]\n",
    "            for course in next_course_set:\n",
    "                if real_time[course] < time[course - 1] + real_time[header]:\n",
    "                    real_time[course] = time[course - 1] + real_time[header]\n",
    "                    res = max(real_time[course], res)\n",
    "                    begin_queue.put(course)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        m = len(relations)\n",
    "        e = [-1] * (m + 7)\n",
    "        he = [-1] * n\n",
    "        ne = [-1] * (m + 7)\n",
    "        deg = [0] * n\n",
    "        idx = 0\n",
    "        pre = defaultdict(set)\n",
    "\n",
    "        def add(a, b):\n",
    "            nonlocal idx\n",
    "            pre[b].add(a)\n",
    "            e[idx] = b\n",
    "            ne[idx] = he[a]\n",
    "            he[a] = idx\n",
    "            deg[b] += 1\n",
    "            idx += 1\n",
    "        \n",
    "        for a, b in relations:\n",
    "            add(a - 1, b - 1)\n",
    "        q = deque()\n",
    "        for i, d in enumerate(deg):\n",
    "            if not d:\n",
    "                q.append(i)\n",
    "        seq = []\n",
    "        # print(q)\n",
    "        while q:\n",
    "            s = len(q)\n",
    "            for _ in range(s):\n",
    "                t = q.popleft()\n",
    "                seq.append(t)\n",
    "                j = he[t]\n",
    "                while j != -1:\n",
    "                    deg[e[j]] -= 1\n",
    "                    if not deg[e[j]]:\n",
    "                        q.append(e[j])\n",
    "                    j = ne[j]\n",
    "        # print(pre)\n",
    "        # print(seq)\n",
    "        f = dict()\n",
    "        ans = 0\n",
    "        for l in seq:\n",
    "            if not pre[l]:\n",
    "                f[l] = time[l]\n",
    "            else:\n",
    "                f[l] = max(f[t] for t in pre[l]) + time[l]\n",
    "            ans = max(ans, f[l])\n",
    "        # print(f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class myHeap:\n",
    "    def __init__(self, data):\n",
    "        self.node_position_map = {}\n",
    "        self.data = []\n",
    "        for cnt, node in data:\n",
    "            self.node_position_map[node] = len(self.data)\n",
    "            self.data.append((cnt, node))\n",
    "            self.shift_up(self.node_position_map[node])\n",
    "        \n",
    "    def shift_up(self, idx):\n",
    "        while idx > 0 and self.data[idx][0] < self.data[(idx-1) // 2][0]:\n",
    "            self.swap(idx, (idx-1) // 2)\n",
    "            idx = (idx - 1) // 2\n",
    "    \n",
    "    def swap(self, idx_x, idx_y):\n",
    "        data_x, data_y = self.data[idx_x], self.data[idx_y]\n",
    "        self.data[idx_x], self.data[idx_y] = self.data[idx_y], self.data[idx_x]\n",
    "        self.node_position_map[data_x[1]], self.node_position_map[data_y[1]] = idx_y, idx_x\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return len(self.data) == 0\n",
    "    \n",
    "    def shift_down(self, idx):\n",
    "        while idx <= (len(self.data) - 1 - 1) // 2:\n",
    "            min_child_idx = idx\n",
    "            if self.data[idx][0] > self.data[idx*2+1][0]:\n",
    "                min_child_idx = idx * 2 + 1\n",
    "            if idx*2 + 2 < len(self.data) and self.data[min_child_idx][0] > self.data[idx*2+2][0]:\n",
    "                min_child_idx = idx * 2 + 2\n",
    "            if idx != min_child_idx:\n",
    "                self.swap(idx, min_child_idx)\n",
    "                idx = min_child_idx\n",
    "            else:\n",
    "                break\n",
    "\n",
    "\n",
    "    def pop(self):\n",
    "        self.swap(0, len(self.data)-1)\n",
    "        pop_cnt, pop_node = self.data.pop(-1)\n",
    "        if not self.isEmpty():\n",
    "            self.shift_down(0)\n",
    "        return pop_cnt, pop_node\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        pre_cnt_map = defaultdict(int)\n",
    "        end_month_map = defaultdict(int)\n",
    "        graph = defaultdict(list)\n",
    "        for src, end in relations:\n",
    "            graph[src].append(end)\n",
    "            pre_cnt_map[end] += 1\n",
    "        myheap = myHeap([(pre_cnt_map[i], i) for i in range(1, n+1)])\n",
    "        max_month = 0\n",
    "        while not myheap.isEmpty():\n",
    "            _, node = myheap.pop()\n",
    "            cur_end_month = end_month_map[node] + time[node-1]\n",
    "            max_month = max(cur_end_month, max_month)\n",
    "            for neigh in graph[node]:\n",
    "                end_month_map[neigh] = max(end_month_map[neigh], cur_end_month)\n",
    "                node_heap_idx = myheap.node_position_map[neigh]\n",
    "                heap_cur_tuple = myheap.data[node_heap_idx]\n",
    "                myheap.data[node_heap_idx] = (heap_cur_tuple[0]-1, heap_cur_tuple[1])\n",
    "                myheap.shift_up(node_heap_idx)\n",
    "        return max_month\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, num, time):\n",
    "        self.num = num\n",
    "        self.time = time\n",
    "        self.next_nodes = set()\n",
    "        self.pre_nodes = 0\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        info = {}\n",
    "        for i in range(1, len(time) + 1):\n",
    "            info[i] = Node(i, time[i - 1])\n",
    "        \n",
    "\n",
    "        for pre_node, node in relations:\n",
    "            info[pre_node].next_nodes.add(info[node])\n",
    "            info[node].pre_nodes += 1\n",
    "        \n",
    "        opts = set()\n",
    "        res = {}\n",
    "        for i in range(1, len(time) + 1):\n",
    "            res[i] = 0\n",
    "        for node in info:\n",
    "            if info[node].pre_nodes == 0:\n",
    "                opts.add(info[node])\n",
    "                res[info[node].num] = info[node].time\n",
    "        \n",
    "\n",
    "        next_opts = None\n",
    "        max_time = 0\n",
    "\n",
    "        while opts:\n",
    "            next_opts = set()\n",
    "            for node in opts:\n",
    "                if node.next_nodes:\n",
    "                    for next_node in node.next_nodes:\n",
    "                        res[next_node.num] = max(res[next_node.num], res[node.num] + next_node.time)\n",
    "                        next_node.pre_nodes -= 1\n",
    "                        if next_node.pre_nodes == 0:\n",
    "                            next_opts.add(next_node)\n",
    "                else:\n",
    "                    max_time = max(max_time, res[node.num])\n",
    "            \n",
    "            opts = next_opts\n",
    "            # print(max_time, res)\n",
    "        \n",
    "        return max_time\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        d, d1 = defaultdict(set), defaultdict(set)\n",
    "        for i, j in relations:\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            d[i].add(j)\n",
    "            d1[j].add(i)\n",
    "        a = [i for i in range(n) if i not in d1]\n",
    "        t = [0] * n\n",
    "        for i in a:\n",
    "            t[i] = time[i]\n",
    "        while a:\n",
    "            a1 = []\n",
    "            for i in a:\n",
    "                for j in d[i]:\n",
    "                    d1[j].remove(i)\n",
    "                    t[j] = max(t[j], t[i])\n",
    "                    if not d1[j]:\n",
    "                        a1.append(j)\n",
    "                        t[j] += time[j]\n",
    "            a = a1\n",
    "        return max(t)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        t = 0\n",
    "        pres = {}  # 需求 key为某课程 value为该课程的前置课程\n",
    "        afters = {}  # 解锁 key为某课程 value为该课程的后续课程\n",
    "        for r in relations:\n",
    "            afters.setdefault(r[0], set()).add(r[1])\n",
    "            pres.setdefault(r[1], set()).add(r[0])\n",
    "        courses = []  # (完成时间， 课程)\n",
    "        heapq.heapify(courses)\n",
    "        for k in set(range(1, n+1)).difference(pres.keys()):\n",
    "            heapq.heappush(courses, (t + time[k-1], k))\n",
    "        while courses:\n",
    "            f_time, course = heapq.heappop(courses)\n",
    "            t = f_time\n",
    "            if course not in afters:\n",
    "                continue\n",
    "            after_courses = afters[course]\n",
    "            for c in after_courses:\n",
    "                pre_courses = pres[c]  # 前置课程\n",
    "                pre_courses.remove(course)\n",
    "                if not pre_courses:\n",
    "                    del pres[c]\n",
    "                    heapq.heappush(courses, (t + time[c-1], c))\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        if len(relations) == 0:\n",
    "            return max(time)\n",
    "        r = np.array(relations)\n",
    "        s, l = set(r[:,1]) ^ set(range(1, n+1)), []\n",
    "        out = {i : [] for i in range(1, n+1)}\n",
    "        in_ = [0 for i in range(0, n+1)]\n",
    "        pre = [0 for i in range(0, n+1)]\n",
    "        res = 0\n",
    "        for p, n in r:\n",
    "            out[p].append(n)\n",
    "            in_[n] += 1\n",
    "        while len(s) != 0:\n",
    "            n = s.pop()\n",
    "            l.append(n)\n",
    "            for o in out[n]:\n",
    "                in_[o] -= 1\n",
    "                if in_[o] == 0:\n",
    "                    s.add(o)\n",
    "        for i in l:\n",
    "            for o in out[i]:\n",
    "                pre[o] = max(pre[o], time[i-1] + pre[i])\n",
    "            res = max(res, time[i-1] + pre[i])\n",
    "            # print(f\"{i=}, {res=}\")\n",
    "        # print(f\"{time=}, {pre=}\")\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        adj1 = {}\n",
    "        adj2 = {}\n",
    "        di = [0] * n\n",
    "        for r in relations:\n",
    "            i = r[0] - 1\n",
    "            o = r[1] - 1\n",
    "            di[o] += 1\n",
    "            if i in adj1:\n",
    "                adj1[i].add(o)\n",
    "            else:\n",
    "                adj1[i] = {o}\n",
    "            if o in adj2:\n",
    "                adj2[o].add(i)\n",
    "            else:\n",
    "                adj2[o] = {i}\n",
    "        adj1[-1] = set()\n",
    "        for i in range(n):\n",
    "            if di[i] == 0:\n",
    "                adj1[-1].add(i)\n",
    "                if i in adj2:\n",
    "                    adj2[i].add(-1)\n",
    "                else:\n",
    "                    adj2[i] = {-1}\n",
    "\n",
    "        res = [math.inf] * (n + 1)\n",
    "        res[-1] = 0\n",
    "        s = adj1[-1]\n",
    "        while len(s) > 0:\n",
    "            new = set()\n",
    "            while len(s) > 0:\n",
    "                l = s.pop()\n",
    "                if l in adj2:\n",
    "                    res[l] = max([res[y] for y in adj2[l]]) + time[l]\n",
    "                if res[l] != math.inf and l in adj1:\n",
    "                    new = new.union(adj1[l])\n",
    "            s = new\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#!/usr/bin/env python3\n",
    "# -*- coding: utf-8 -*-\n",
    "# Xiang Wang <ramwin@qq.com>\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，\n",
    "其中 relations[j] = [prevCoursej, nextCoursej] ，表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）。\n",
    "同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode.cn/problems/parallel-courses-iii\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "import logging\n",
    "import heapq\n",
    "from decimal import Decimal\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Course:\n",
    "    \"\"\"课程对象\"\"\"\n",
    "\n",
    "    def __init__(self, _id, cost: int, end_time=Decimal('inf')):\n",
    "        \"\"\"\n",
    "        cost: 课程需要花费的月份数\n",
    "        \"\"\"\n",
    "        self._id = _id\n",
    "        self.cost = cost\n",
    "        self.end_time = end_time  # 默认\n",
    "        self.prev = set()  # 保存的是Course对象\n",
    "        self.next = set()  # prev和next随着时间的流逝会pop\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.end_time < other.end_time\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self._id == other._id\n",
    "\n",
    "    def __hash__(self):\n",
    "        return self._id\n",
    "\n",
    "\n",
    "class Solution1:\n",
    "    \"\"\"\n",
    "    模拟现实状况. 死循环, 每次时间跳转到最近完成的课程, 把最近完成的课程加入学习队列\n",
    "    执行用时： 676 ms , 在所有 Python3 提交中击败了 5.47% 的用户\n",
    "    内存消耗： 68.5 MB , 在所有 Python3 提交中击败了 22.65% 的用户\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, relations, times):\n",
    "        self.course_dict = self.create_course(times)\n",
    "        self.init_relations(relations)\n",
    "        # 每次都要pop最近完成的课程\n",
    "        self.current_learning = self.init_start_learning_courses()\n",
    "        self.time = 0\n",
    "\n",
    "    def get_result(self):\n",
    "        while self.current_learning:\n",
    "            first_end_course = heapq.heappop(self.current_learning)\n",
    "            self.time = first_end_course.end_time\n",
    "            for next_course in first_end_course.next:\n",
    "                next_course.prev.remove(first_end_course)\n",
    "                if not next_course.prev:\n",
    "                    next_course.end_time = self.time + next_course.cost\n",
    "                    heapq.heappush(\n",
    "                        self.current_learning,\n",
    "                        next_course,\n",
    "                    )\n",
    "        return self.time\n",
    "\n",
    "    def create_course(self, times):\n",
    "        \"\"\"创建所有课程\"\"\"\n",
    "        course_dict = {\n",
    "        }\n",
    "        for index, time in enumerate(times):\n",
    "            course_dict[index+1] = Course(\n",
    "                _id=index+1,\n",
    "                cost=time,\n",
    "            )\n",
    "        return course_dict\n",
    "\n",
    "    def init_relations(self, relations):\n",
    "        for pre_id, next_id in relations:\n",
    "            self.course_dict[pre_id].next.add(\n",
    "                self.course_dict[next_id]\n",
    "            )\n",
    "            self.course_dict[next_id].prev.add(\n",
    "                self.course_dict[pre_id]\n",
    "            )\n",
    "\n",
    "    def init_start_learning_courses(self):\n",
    "        \"\"\"找到所有没有依赖的课程, 加入current_learning\"\"\"\n",
    "        results = []\n",
    "        for course in self.course_dict.values():\n",
    "            if not course.prev:\n",
    "                course.end_time = course.cost\n",
    "                results.append(course)\n",
    "        heapq.heapify(results)\n",
    "        return results\n",
    "\n",
    "\n",
    "class Solution2:\n",
    "    \"\"\"\n",
    "    递归. 每个课程的完成时间, 等于课程时间+前置依赖的课程的完成时间\n",
    "\n",
    "    执行用时： 836 ms , 在所有 Python3 提交中击败了 5.47% 的用户\n",
    "    内存消耗： 156 MB , 在所有 Python3 提交中击败了 5.46% 的用户\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, relations, times):\n",
    "        self.course_dict = self.create_course(times)\n",
    "        self.init_relations(relations)\n",
    "        # 每次都要pop最近完成的课程\n",
    "\n",
    "    def get_result(self):\n",
    "        end_time = 0\n",
    "        for course in self.course_dict.values():\n",
    "            if course.end_time is None:\n",
    "                course.end_time = self.get_end_time(course)\n",
    "            if course.end_time > end_time:\n",
    "                end_time = course.end_time\n",
    "        return end_time\n",
    "\n",
    "    def get_end_time(self, course) -> int:\n",
    "        \"\"\"\n",
    "        递归地获取课程的结束时间\n",
    "        \"\"\"\n",
    "        if course.end_time is not None:\n",
    "            return course.end_time\n",
    "        if not course.prev:\n",
    "            course.end_time = course.cost\n",
    "            return course.cost\n",
    "        course.end_time = max((\n",
    "            self.get_end_time(course)\n",
    "            for course in course.prev\n",
    "        )) + course.cost\n",
    "        return course.end_time\n",
    "\n",
    "    def create_course(self, times):\n",
    "        \"\"\"创建所有课程\"\"\"\n",
    "        course_dict = {\n",
    "        }\n",
    "        for index, time in enumerate(times):\n",
    "            course_dict[index+1] = Course(\n",
    "                _id=index+1,\n",
    "                cost=time,\n",
    "                end_time=None\n",
    "            )\n",
    "        return course_dict\n",
    "\n",
    "    def init_relations(self, relations):\n",
    "        for pre_id, next_id in relations:\n",
    "            self.course_dict[pre_id].next.add(\n",
    "                self.course_dict[next_id]\n",
    "            )\n",
    "            self.course_dict[next_id].prev.add(\n",
    "                self.course_dict[pre_id]\n",
    "            )\n",
    "\n",
    "\n",
    "class Course3:\n",
    "    \"\"\"课程对象\"\"\"\n",
    "\n",
    "    def __init__(self, _id, cost: int, end_time=Decimal('inf')):\n",
    "        \"\"\"\n",
    "        cost: 课程需要花费的月份数\n",
    "        \"\"\"\n",
    "        self._id = _id\n",
    "        self.cost = cost\n",
    "        self.end_time = end_time  # 默认\n",
    "        self.prev = set()  # 保存的是Courseid\n",
    "        self.next = set()  # prev和next随着时间的流逝会pop\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.end_time < other.end_time\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self._id == other._id\n",
    "\n",
    "    def __hash__(self):\n",
    "        return self._id\n",
    "\n",
    "\n",
    "class Solution3:\n",
    "    \"\"\"\n",
    "    优化Solution1, 用id来保存prev和next\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, relations, times):\n",
    "        self.course_dict = self.create_course(times)\n",
    "        self.init_relations(relations)\n",
    "        # 每次都要pop最近完成的课程\n",
    "        self.current_learning = self.init_start_learning_courses()\n",
    "        self.time = 0\n",
    "\n",
    "    def get_result(self):\n",
    "        while self.current_learning:\n",
    "            first_end_course = heapq.heappop(self.current_learning)\n",
    "            self.time = first_end_course.end_time\n",
    "            for next_course_id in first_end_course.next:\n",
    "                next_course = self.course_dict[next_course_id]\n",
    "                next_course.prev.remove(first_end_course._id)\n",
    "                if not next_course.prev:\n",
    "                    next_course.end_time = self.time + next_course.cost\n",
    "                    heapq.heappush(\n",
    "                        self.current_learning,\n",
    "                        next_course,\n",
    "                    )\n",
    "        return self.time\n",
    "\n",
    "    def create_course(self, times):\n",
    "        \"\"\"创建所有课程\"\"\"\n",
    "        course_dict = {\n",
    "        }\n",
    "        for index, time in enumerate(times):\n",
    "            course_dict[index+1] = Course(\n",
    "                _id=index+1,\n",
    "                cost=time,\n",
    "            )\n",
    "        return course_dict\n",
    "\n",
    "    def init_relations(self, relations):\n",
    "        for pre_id, next_id in relations:\n",
    "            self.course_dict[pre_id].next.add(\n",
    "                next_id\n",
    "            )\n",
    "            self.course_dict[next_id].prev.add(\n",
    "                pre_id\n",
    "            )\n",
    "\n",
    "    def init_start_learning_courses(self):\n",
    "        \"\"\"找到所有没有依赖的课程, 加入current_learning\"\"\"\n",
    "        results = []\n",
    "        for course in self.course_dict.values():\n",
    "            if not course.prev:\n",
    "                course.end_time = course.cost\n",
    "                results.append(course)\n",
    "        heapq.heapify(results)\n",
    "        return results\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"题目框架\"\"\"\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        logging.info(n)\n",
    "        return Solution3(\n",
    "            relations=relations,\n",
    "            times=time,\n",
    "        ).get_result()\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    print(\n",
    "        Solution().minimumTime(\n",
    "            n=3,\n",
    "            relations=[[1, 3], [2, 3]],\n",
    "            time=[3, 2, 5],\n",
    "        )\n",
    "    )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        requires = collections.defaultdict(set)\n",
    "        enables = collections.defaultdict(set)\n",
    "        for pc, nc in relations :\n",
    "            requires[nc-1].add(pc-1)\n",
    "            enables[pc-1].add(nc-1)\n",
    "        \n",
    "        heap = []\n",
    "        for i in range(n) :\n",
    "            if len(requires[i]) == 0 :\n",
    "                heapq.heappush(heap, [time[i], i])\n",
    "        \n",
    "        while len(heap) > 0 :\n",
    "            tnow, cid = heapq.heappop(heap)\n",
    "            for nextc in enables[cid] :\n",
    "                requires[nextc].remove(cid)\n",
    "                if len(requires[nextc]) == 0 :\n",
    "                    heapq.heappush(heap, [tnow+time[nextc], nextc])\n",
    "        \n",
    "            if len(heap) == 0 :\n",
    "                return tnow\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        pre = defaultdict(set)\n",
    "        nex = defaultdict(list)\n",
    "        f = set(range(1,n+1))\n",
    "        for p,q in relations:\n",
    "            pre[q].add(p)\n",
    "            nex[p].append(q)\n",
    "            if q in f:\n",
    "                f.remove(q)\n",
    "        v = set(f)\n",
    "        t2c = defaultdict(set)\n",
    "        for i in f:\n",
    "            t2c[time[i-1]].add(i)\n",
    "        fint = list(t2c.keys())\n",
    "        import heapq\n",
    "        heapq.heapify(fint)\n",
    "        while fint:\n",
    "            t = heapq.heappop(fint)\n",
    "            for c in t2c[t]:\n",
    "                for i in nex[c]:\n",
    "                    pre[i].remove(c)\n",
    "                    if len(pre[i])==0:\n",
    "                        _t = t + time[i-1]\n",
    "                        if _t not in t2c:\n",
    "                            heapq.heappush(fint,_t)\n",
    "                        t2c[_t].add(i)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        return run(n, relations, time)\n",
    "def run(n, relations, times):\n",
    "\tfrom sortedcontainers import SortedList\n",
    "\tprev = collections.defaultdict(SortedList)\n",
    "\tafter = collections.defaultdict(list)\n",
    "\tfor x, y in relations:\n",
    "\t\tprev[y].add(x)\n",
    "\t\tafter[x].append(y)\n",
    "\tq = []\n",
    "\tfor i in range(1, n + 1):\n",
    "\t\tif len(prev[i]) == 0:\n",
    "\t\t\tq.append([times[i - 1], i])\n",
    "\theapq.heapify(q)\n",
    "\tmt = 0\n",
    "\twhile len(q) > 0:\n",
    "\t\tt, node = heapq.heappop(q)\n",
    "\t\tnnodes = after[node]\n",
    "\t\tmt = t\n",
    "\t\tif len(nnodes) == 0:\n",
    "\t\t\tcontinue\n",
    "\t\tfor i in nnodes:\n",
    "\t\t\tif len(prev[i]) == 1:\n",
    "\t\t\t\theapq.heappush(q, [t + times[i - 1], i])\n",
    "\t\t\telse:\n",
    "\t\t\t\tprev[i].remove(node)\n",
    "\treturn mt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        dic = {}\n",
    "        rlen = len(relations)\n",
    "        record = [0 for i in range(n+1)]\n",
    "        month = [0 for i in range(n+1)]\n",
    "        MT = [0 for i in range(n+1)]\n",
    "        for i in range(n):\n",
    "            month[i+1] = time[i]\n",
    "            MT[i+1] = time[i]\n",
    "        for i in range(rlen):\n",
    "            record[relations[i][0]] = 1\n",
    "            if dic.get(relations[i][1]) == None:\n",
    "                dic[relations[i][1]] = [relations[i][0]]\n",
    "            else:\n",
    "                dic[relations[i][1]].append(relations[i][0])\n",
    "        for i in range(1, n+1):\n",
    "            if record[i] == 0:\n",
    "                self.visit(dic, month, i, MT)\n",
    "        # print(month)\n",
    "        # print(MT)\n",
    "        return max(MT)\n",
    "                \n",
    "    def visit(self, dic, month, i, MT):\n",
    "        if dic.get(i) == None:\n",
    "            return\n",
    "        for temp in dic[i]:\n",
    "            T = month[temp] + MT[i]\n",
    "            if T > MT[temp]:\n",
    "                MT[temp] = T\n",
    "                self.visit(dic, month, temp, MT)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        acc = time.copy()\n",
    "        ret = max(acc)\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for rel in relations:\n",
    "            adj[rel[0]-1].append(rel[1]-1)\n",
    "        vis = [0 for _ in range(n)]\n",
    "        topo = []\n",
    "        def dfs(cur):\n",
    "            if vis[cur]:\n",
    "                return\n",
    "            vis[cur] = 1\n",
    "            for nxt in adj[cur]:\n",
    "                dfs(nxt)\n",
    "            topo.append(cur)\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        for u in topo[::-1]:\n",
    "            for v in adj[u]:\n",
    "                acc[v] = max(acc[u] + time[v], acc[v])\n",
    "                ret = max(ret, acc[v])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        pre = defaultdict(set)\n",
    "        nex = defaultdict(set)\n",
    "        f = set(range(1,n+1))\n",
    "        for p,q in relations:\n",
    "            pre[q].add(p)\n",
    "            nex[p].add(q)\n",
    "            if q in f:\n",
    "                f.remove(q)\n",
    "        v = set(f)\n",
    "        t2c = defaultdict(set)\n",
    "        for i in f:\n",
    "            t2c[time[i-1]].add(i)\n",
    "        fint = list(t2c.keys())\n",
    "        import heapq\n",
    "        heapq.heapify(fint)\n",
    "        while fint:\n",
    "            t = heapq.heappop(fint)\n",
    "            for c in t2c[t]:\n",
    "                for i in nex[c]:\n",
    "                    pre[i].remove(c)\n",
    "                    if len(pre[i])==0:\n",
    "                        _t = t + time[i-1]\n",
    "                        if _t not in t2c:\n",
    "                            heapq.heappush(fint,_t)\n",
    "                        t2c[_t].add(i)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        self.time = time\n",
    "        self.relats = [[] for _ in range(n+1)]\n",
    "        self.cost = [0] * (n + 1)\n",
    "        for prev, next in relations:\n",
    "            self.relats[next].append(prev)\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            res = max(res, self.dfs(i))\n",
    "        return res\n",
    "\n",
    "    def dfs(self, cur):\n",
    "        if self.cost[cur] > 0:\n",
    "            return self.cost[cur]\n",
    "        self.cost[cur] = self.time[cur - 1]\n",
    "        max_res = 0\n",
    "        for pre in self.relats[cur]:\n",
    "            max_res = max(max_res, self.dfs(pre))\n",
    "        self.cost[cur] += max_res\n",
    "        return self.cost[cur]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        graph = [[] for _ in range(len(time)+1)]\n",
    "        visited = [-1]*(len(time)+1)\n",
    "        for s in relations:\n",
    "            graph[s[1]].append(s[0])\n",
    "        def traverse(graph,i):\n",
    "            if visited[i] != -1:\n",
    "                return visited[i]\n",
    "            if not graph[i]:\n",
    "                return time[i-1]\n",
    "            mtime = 0\n",
    "            for j in graph[i]:\n",
    "                mtime = max(mtime,traverse(graph,j))\n",
    "            visited[i] = mtime+time[i-1]\n",
    "            return visited[i]\n",
    "        maxtime = 0\n",
    "        for i in range(1,len(graph)):\n",
    "\n",
    "            maxtime = max(maxtime,traverse(graph,i))\n",
    "        return maxtime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        # dic = {}\n",
    "        # for i in range(1, n+1):\n",
    "        #     dic[i] = time[i-1]\n",
    "        # altered = True\n",
    "        # answer = max(time) \n",
    "        # while altered:\n",
    "        #     altered = False\n",
    "        #     for i in range(1, n+1):\n",
    "        #         for r in relations:\n",
    "        #             if i == r[1]:\n",
    "        #                 if time[i-1] + dic[r[0]] > dic[i]:\n",
    "        #                     altered = True\n",
    "        #                     dic[i] = time[i-1] + dic[r[0]]\n",
    "        #                     answer = max(answer, dic[i])\n",
    "        \n",
    "        # return answer\n",
    "        dependencies = [[] for i in range(n)]\n",
    "        for r in relations:\n",
    "            dependencies[r[1] - 1].append(r[0])\n",
    "        classes = {}\n",
    "\n",
    "        def dp(i):\n",
    "            if i in classes:\n",
    "                return classes[i]\n",
    "            current = 0\n",
    "            for p in dependencies[i - 1]:\n",
    "                current = max(current, dp(p))\n",
    "            current += time[i - 1]\n",
    "            classes[i] = current\n",
    "            return current\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dp(i + 1))\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recursion(self,dic,last,time,count):\n",
    "        if not dic.get(last):\n",
    "            return 0\n",
    "        nodelist = dic.get(last)\n",
    "        res = 0\n",
    "        for i in range(len(nodelist)):\n",
    "            index = nodelist[i]-1\n",
    "            if count[index]!=0:\n",
    "                res = max(res,count[index])\n",
    "                # print(last,res)\n",
    "            else:\n",
    "                count[index] = time[index]+self.recursion(dic,nodelist[i],time,count)\n",
    "                res = max(res,count[index])\n",
    "            # print(nodelist[i],time[nodelist[i]-1],res)\n",
    "        return res\n",
    "\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        if not relations:\n",
    "            return max(time)\n",
    "        dic = {}\n",
    "        for rel in relations:\n",
    "            if rel[1] not in dic:\n",
    "                dic[rel[1]] = [rel[0]]\n",
    "            else:\n",
    "                dic[rel[1]].append(rel[0])\n",
    "        # for i in range(n):\n",
    "        #     if i+1 not in dic:\n",
    "        #         dic[i+1] = None\n",
    "        res = [0 for _ in range(n)]\n",
    "        j = 0\n",
    "        count = 0\n",
    "        for j in range(n):\n",
    "            key = j+1\n",
    "            # print(self.recursion(dic,key,time[key-1],time))\n",
    "            # print(key)\n",
    "            res[j] = time[j]+self.recursion(dic,key,time,res)\n",
    "            # print(key,res,dic.get(key))\n",
    "            count = max(count,res[j])\n",
    "            \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        \n",
    "        degree = [0]*n\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in relations:\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            dct[i].append(j)\n",
    "            degree[j] += 1\n",
    "        \n",
    "        dp = [0]*n\n",
    "        \n",
    "        stack = [i for i in range(n) if not degree[i]]\n",
    "        for i in stack:\n",
    "            dp[i] = time[i]\n",
    "        \n",
    "        def dfs(a):\n",
    "            \n",
    "            for b in dct[a]:\n",
    "                if dp[a] > dp[b]:\n",
    "                    dp[b] = dp[a]\n",
    "                degree[b] -= 1\n",
    "                if not degree[b]:\n",
    "                    dp[b] += time[b]\n",
    "                    dfs(b)\n",
    "            return\n",
    "        \n",
    "        for i in stack:\n",
    "            dfs(i)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        # cache the max_time for each node\n",
    "        # build the adjacency list\n",
    "        adjacency = defaultdict(list)\n",
    "        for src, dst in relations:\n",
    "            adjacency[src].append(dst)\n",
    "        \n",
    "        cache = {} # node: max_time\n",
    "        def dfs(src):\n",
    "            if src in cache:\n",
    "                return cache[src]\n",
    "            result = time[src - 1] # time is 0-index\n",
    "            for nei in adjacency[src]:\n",
    "                result = max(result, time[src - 1] + dfs(nei))\n",
    "            cache[src] = result\n",
    "            return result\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dfs(i)\n",
    "        return max(cache.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "    \tpre_v = [[] for i in time]\n",
    "    \tfor i,j in relations:\n",
    "    \t\tpre_v[j - 1].append(i - 1)\n",
    "    \tmem = {}\n",
    "    \tdef dp(i,mem,time,pre_v):\n",
    "    \t\tcur_time = 0\n",
    "    \t\tfor j in pre_v[i]:\n",
    "    \t\t\tif j not in mem:\n",
    "    \t\t\t\tpre_time = dp(j,mem,time,pre_v)\n",
    "    \t\t\telse:\n",
    "    \t\t\t\tpre_time = mem[j]\n",
    "    \t\t\tcur_time = max(cur_time,pre_time)\n",
    "    \t\tmem[i] = cur_time + time[i]\n",
    "    \t\treturn cur_time + time[i]\n",
    "    \tmax_time = 0\n",
    "    \tfor i in range(len(pre_v)):\n",
    "    \t\tmax_time = max(max_time,dp(i,mem,time,pre_v))\n",
    "    \treturn max_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_time(self, class_id, graph, time, learn_time):\n",
    "        if learn_time[class_id - 1] != -1:\n",
    "            return learn_time[class_id - 1]\n",
    "\n",
    "        if class_id not in graph:\n",
    "            learn_time[class_id - 1] = time[class_id - 1]\n",
    "            return time[class_id - 1]\n",
    "\n",
    "        class_time = time[class_id - 1]\n",
    "        next_time = 0\n",
    "        for pre in graph[class_id]:\n",
    "            pre_time = self.get_time(pre, graph, time, learn_time)\n",
    "            next_time = max(next_time, pre_time + class_time)\n",
    "\n",
    "        learn_time[class_id - 1] = next_time\n",
    "        return next_time\n",
    "\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        graph = defaultdict(set)\n",
    "\n",
    "        for pre, next in relations:\n",
    "            graph[next].add(pre)\n",
    "\n",
    "        learn_time = [-1] * n\n",
    "        max_time = 0\n",
    "        for i in range(1, n+1):\n",
    "            max_time = max(max_time, self.get_time(i, graph, time, learn_time))\n",
    "\n",
    "            # if learn_time[i-1] != -1:\n",
    "            #     max_time = max(max_time, learn_time[i-1])\n",
    "            #     continue\n",
    "\n",
    "        # print(learn_time)\n",
    "\n",
    "        return max_time\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        res = 0\n",
    "        graph = defaultdict(set)\n",
    "        memo = defaultdict(int)\n",
    "\n",
    "        for cls1, cls2 in relations:\n",
    "            graph[cls1].add(cls2)      \n",
    "\n",
    "        def calc(i):\n",
    "            if i not in memo:\n",
    "                l = 0\n",
    "                for c in graph[i]:\n",
    "                    l = max(l, calc(c))\n",
    "                l += time[i - 1]\n",
    "                memo[i] = l\n",
    "            return memo[i]\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            res = max(res, calc(i))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        res = 0\n",
    "        graph = defaultdict(set)\n",
    "        memo = defaultdict(int)\n",
    "\n",
    "        for cls1, cls2 in relations:\n",
    "            graph[cls2].add(cls1)      \n",
    "\n",
    "        def calc(i):\n",
    "            if i not in memo:\n",
    "                l = 0\n",
    "                for c in graph[i]:\n",
    "                    l = max(l, calc(c))\n",
    "                l += time[i - 1]\n",
    "                memo[i] = l\n",
    "            return memo[i]\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            res = max(res, calc(i))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        mx = 0\n",
    "        prev = [[] for _ in range(n + 1)]\n",
    "        for x, y in relations:\n",
    "            prev[y].append(x)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i: int) -> int:\n",
    "            cur = 0\n",
    "            for p in prev[i]:\n",
    "                cur = max(cur, dp(p))\n",
    "            cur += time[i - 1]\n",
    "            return cur\n",
    "            \n",
    "        for i in range(1, n + 1):\n",
    "            mx = max(mx, dp(i))\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        parents = [[] for _ in range(n+1)]\n",
    "        for a,b in relations:\n",
    "            parents[b].append(a)\n",
    "\n",
    "        @cache\n",
    "        def func1(i):\n",
    "            d = time[i-1]\n",
    "            res = 0\n",
    "            for j in parents[i]:\n",
    "                res = max(res, func1(j))\n",
    "            return res + d \n",
    "\n",
    "        res = 0\n",
    "        for i in range(1,n+1):\n",
    "            timelen = func1(i)\n",
    "            res = max(res, timelen)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        mx = 0\n",
    "        prev = [[] for _ in range(n)]\n",
    "        for x, y in relations:\n",
    "            prev[y-1].append(x-1)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i: int) -> int:\n",
    "            cur = 0\n",
    "            for p in prev[i]:\n",
    "                cur = max(cur, dp(p))\n",
    "            cur += time[i]\n",
    "            return cur\n",
    "            \n",
    "        for i in range(n):\n",
    "            mx = max(mx, dp(i))\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        mx = 0\n",
    "        prev = [[] for _ in range(n + 1)]\n",
    "        for x, y in relations:\n",
    "            prev[y-1].append(x-1)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i: int) -> int:\n",
    "            cur = 0\n",
    "            for p in prev[i]:\n",
    "                cur = max(cur, dp(p))\n",
    "            cur += time[i]\n",
    "            return cur\n",
    "            \n",
    "        for i in range(n):\n",
    "            mx = max(mx, dp(i))\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "\t\tparents = [[] for _ in range(n)]\n",
    "\t\t\n",
    "\t\tfor pre, next in relations:\n",
    "\t\t\tparents[next-1].append(pre-1)\n",
    "\t\t\n",
    "\t\t@cache\n",
    "\t\tdef func1(curr):\n",
    "\t\t\tlst = parents[curr]\n",
    "\t\t\t\n",
    "\t\t\tif not lst:\n",
    "\t\t\t\treturn time[curr]\n",
    "\t\t\tres = 0\n",
    "\t\t\tfor v in lst:\n",
    "\t\t\t\tres = max(res,func1(v))\n",
    "\t\t\treturn res + time[curr]\n",
    "\t\t\n",
    "\t\tres = 0\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tres = max(res,func1(i))\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            rel = 0\n",
    "            for j in d[i]:\n",
    "                rel = max(rel,dfs(j))\n",
    "            return rel+time[i]\n",
    "        ans = 0\n",
    "        from collections import defaultdict\n",
    "        d = defaultdict(list)\n",
    "        for a,b in relations:\n",
    "            d[b-1].append(a-1)\n",
    "        for i in range(n):\n",
    "            ans = max(ans,dfs(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        g=[[] for _ in range(n+1)]\n",
    "        rg=[[] for _ in range(n+1)]\n",
    "        indegree=[0]*(n+1)\n",
    "        for a,b in relations:\n",
    "            g[a].append(b)\n",
    "            rg[b].append(a)\n",
    "            indegree[b]+=1\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            ans=0\n",
    "            for j in g[i]:\n",
    "                ans=max(ans,dfs(j))\n",
    "            return ans+time[i-1]\n",
    "        res=0\n",
    "        for i in range(1,n+1):\n",
    "            res=max(dfs(i),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], times: List[int]) -> int:\n",
    "        graph = {i:[] for i in range(1,n+1)}\n",
    "        for prev, nxt in relations:\n",
    "            graph[nxt].append(prev)\n",
    "        dp = [0 for _ in range(n)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if len(graph[i])==0:\n",
    "                # 当前课程没有前置，直接返回\n",
    "                dp[i-1] = times[i-1]\n",
    "                return times[i-1]\n",
    "            preg = graph[i]\n",
    "            for p in preg:\n",
    "                dp[i-1] = max(dp[i-1], dfs(p)+times[i-1])\n",
    "            return dp[i-1]\n",
    "        for i in range(1, n+1):\n",
    "            dfs(i)\n",
    "        return max(dp)\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        indegs = [set() for _ in range(n)]\n",
    "        for prev_course, next_course in relations:\n",
    "            indegs[prev_course - 1].add(next_course - 1)\n",
    "        @cache\n",
    "        def memorysearch(course: int) -> int:\n",
    "            cost = 0\n",
    "            for prev in indegs[course]:\n",
    "                cost = max(cost, memorysearch(prev))\n",
    "            cost += time[course]\n",
    "            return cost\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, memorysearch(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        @cache\n",
    "        def DFS(n):\n",
    "            res = 0\n",
    "            for x in arr[n]:\n",
    "                res = max(res, DFS(x))\n",
    "            \n",
    "            return res + time[n]\n",
    "        \n",
    "        arr = [set() for _ in range(n)]\n",
    "        for a, b in relations:\n",
    "            arr[b-1].add(a-1)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, DFS(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        children = defaultdict(list)\n",
    "        father = {}\n",
    "        for pre_c, next_c in relations:\n",
    "            children[next_c].append(pre_c)\n",
    "            father[pre_c] = next_c\n",
    "        for i in range(1, n+1):\n",
    "            if i not in father:\n",
    "                children[-1].append(i)\n",
    "        # print(children)\n",
    "        \n",
    "        newcost = {i:time[i-1] for i in range(1, n+1)}\n",
    "        newcost[-1] = 0\n",
    "        cost = {i:time[i-1] for i in range(1, n+1)}\n",
    "        cost[-1] = 0\n",
    "        @cache\n",
    "        def houxu(root):\n",
    "            if root not in children:\n",
    "                return\n",
    "            for child in children[root]:\n",
    "                houxu(child)\n",
    "                cost[root] = max(cost[root], newcost[root]+cost[child])\n",
    "        houxu(-1)\n",
    "        return cost[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(now):\n",
    "            res = []\n",
    "            for ii in g[now]:\n",
    "                res.append(dfs(ii))\n",
    "            # print(now, res)\n",
    "            return (max(res) if res else 0) + time[now - 1]\n",
    "        g, k = defaultdict(list), defaultdict(list)\n",
    "        for ii, jj in relations:\n",
    "            # print(ii, jj)\n",
    "            g[jj].append(ii)\n",
    "            k[ii].append(jj)\n",
    "        # print(k, g)\n",
    "        res = 0\n",
    "        for ii in range(1, n + 1):\n",
    "            if len(k[ii]) == 0:\n",
    "                res = max(res, dfs(ii))\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n",
    "        mx = 0\n",
    "        prev = [[] for _ in range(n + 1)]\n",
    "        for x, y in relations:\n",
    "            prev[y].append(x)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i):\n",
    "            cur=0\n",
    "            for p in prev[i]:\n",
    "                cur = max(cur,dp(p))\n",
    "            cur +=time[i-1]\n",
    "            return cur\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            mx=max(mx,dp(i))\n",
    "        \n",
    "        return mx"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
